package com.ryujung.dp.leetCode_5;

/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 */

// @lc code=start
/**
 * 思路： 
 * 1. 遍历所有的字符串，找到前后符合回文子串特征的字符串
 * 
 * 回文特征： aba型或者abba型两种
 * 
 */
class Solution {

    /**
     * 中心扩散法，遍历整个字符串，寻找对称的字符
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;

        String result = "";
        for (int i = 0; i < s.length(); i++) {
            String oddMaxStr = getMaxSubstr(s, i, i);
            String evenMaxStr = getMaxSubstr(s, i, i + 1);

            if (oddMaxStr.length() > result.length() || evenMaxStr.length() > result.length()) {
                result = oddMaxStr.length() > evenMaxStr.length() ? oddMaxStr : evenMaxStr;
            }
        }
        return result;
    }

    /**
     * 扩散法寻找符合子串条件的最大子串方法
     * @param s 被查找的子串
     * @param l 扩散的左起点角标
     * @param r 扩散的右起点角标
     * @return 返回在s中，从l向左、r向右完全对称的最长子串
     */
    public static String getMaxSubstr(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        // substring方法包含头不包含尾，
        return l + 1 <= r - 1 ? s.substring(l + 1, r) : "";
    }

    /**
     * 动态规划求解
     * 思路：
     * 将整个问题分解为判断每个子串是否为回文子串
     * 并从中取出长度最大的回文子串
     */
    public static String longestPalindrome2(String s) {
        int l = s.length();
        boolean[][] dp = new boolean[l][l];

        String result = "";
        for (int i = l - 1; i >= 0; i--) {
            for (int j = i; j < l; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || Math.abs(i - j) == 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    if (j - i + 1 > result.length() && dp[i][j]) {
                        result = s.substring(i, j + 1);
                    }
                }

            }
        }
        return result;
    }

    /**
     * 马拉车算法实现
     * [马拉车算法原理](https://www.cnblogs.com/cloudplankroader/p/10988844.html)
     * 大致原理：
     * 首先通过暴力匹配获取一个一定长度的回文子串， 
     * 根据这个回文子串
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static String longestPalindrome3(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        char[] chs = new char[s.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            chs[i] = (i & 1) == 1 ? s.charAt(index++) : '#';
        }
        // 构造一个只需要考虑基数回文的情况，便于后面的判断
        String manacherStr = new String(chs);

        // 以index为中心的回文半径长度
        int[] radiusArr = new int[manacherStr.length()];
        int C = -1;
        int right = -1;
        for (int i = 0; i < manacherStr.length(); i++) {
            // 根据当前已知的最大回文中心和半径，获取当前回文中心的最小回文半径
            radiusArr[i] = i < right ? radiusArr[C - (i - C)] : 1;
            // 
            while (i + radiusArr[i] < manacherStr.length() && i - radiusArr[i] >= 0
                    && manacherStr.charAt(i + radiusArr[i]) == manacherStr.charAt(i - radiusArr[i])) {
                radiusArr[i]++;
                C = i + radiusArr[i] > right ? i : C;
                right = i + radiusArr[i] > right ? i + radiusArr[i] : right;
            }
        }
        // FIXME 算法存在问题，需要修复，否则无法使用
        // TODO 算法存在问题，需要修复，否则无法使用
        String result = manacherStr.substring(C - (right - C), right + 1);
        return result;
    }


    public static void main(String[] args) {
        String testStr = "aacabdkacaa";
        String result = longestPalindrome3(testStr);
        System.out.println("result:" + result); // aca
    }

}
// @lc code=end
